package day10.problem1;

import java.util.*;


public class Solution2 {
    public int getLongestPalindrome (String A) {
        // write code here
        A = " " + A;
        int n = A.length();
        int ret = 0;
        int[][] dp = new int[n][n];
        for(int i = 1; i<n; i++) {
            for(int j = i; j>=0; j--) {
                if(A.charAt(i) == A.charAt(j)){
                    if(i == j) dp[j][i] = 1;
                    else if(j + 1 == i) dp[j][i] = 2;
                    else if(dp[j+1][i-1] != 0) dp[j][i] = dp[j+1][i-1] + 2;
                }
                ret = Math.max(ret, dp[j][i]);
            }
        }
        return ret;
    }
}